package stackOJ;

import java.util.Stack;

//将递归转化为循环：逆序打印链表
public class Solution {
    static class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public Node head;

    public void creatTest() {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        head = node1;
    }

    //逆序打印链表
    public void printList(Node head) {
        if (head == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        while (!stack.empty()) {
            System.out.print(stack.pop().val + " ");
        }
    }


    //括号匹配
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                //左括号少
                if (stack.empty()) {
                    return false;
                }

                char ch2 = stack.peek();
                if (ch2 == '{' && ch == '}' || ch2 == '(' && ch == ')' || ch2 == '[' && ch == ']') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        //右括号少
        if (!stack.empty()) {
            return false;
        }
        return true;
    }

    //逆波兰表达式求值
    //输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String x : tokens) {
            if (!x.equals("+") && !x.equals("-") && !x.equals("*") && !x.equals("/")) {
                stack.push(Integer.parseInt(x));
            } else {
                int num1 = stack.pop();
                int num2 = stack.pop();
                switch (x) {
                    case "+":
                        stack.push(num2 + num1);
                        break;
                    case "-":
                        stack.push(num2 - num1);
                        break;
                    case "*":
                        stack.push(num2 * num1);
                        break;
                    case "/":
                        stack.push(num2 / num1);
                        break;
                }
            }
        }
        return stack.pop();
    }

    //栈的压入、弹出序列
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            //stack.peek().equals(popA[j])魔鬼细节！！！
            while (!stack.empty() && j < popA.length && stack.peek().equals(popA[j])) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] tokens = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
        System.out.println(solution.evalRPN(tokens));


    }

    public static void main1(String[] args) {
        Solution solution = new Solution();
        solution.creatTest();
        solution.printList(solution.head);
    }


}
